"""
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

from leetcode_test import ListNode


class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return
        l = []
        while head:
            l.append(head)
            head = head.next

        i = 0
        j = len(l) - 1

        while i < j:
            l[i].next = l[j]
            i += 1
            if i == j:
                break
            l[j].next = l[i]
            j -= 1
        l[j].next = None
        return l[0]


if __name__ == "__main__":
    head = ListNode.create([1, 2, 3, 4, 5])
    print(head.get_value())
